# @before-stub-for-debug-begin
from python3problem887 import *
from typing import *
# @before-stub-for-debug-end

#
# @lc app=leetcode.cn id=887 lang=python3
#
# [887] 鸡蛋掉落
#

# @lc code=start
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        """
        dp(k, n)第n层k个鸡蛋最少需要移动多少次

        """
        # dp = [[0]*(n+1) for _ in range(k+1)]
        # dp[1][:] = range(0, n+1)

        # for i in range(2, k+1):
        #     for j in range(1, n+1):
        #         res = float("INF")
        #         # for c in range(1, j+1):
        #         #     res = min(res, max(dp[i][j-c], dp[i-1][c-1])+1)
        #         l, r = 1, j
        #         while(l <= r):
        #             m = (l+r) // 2

        #             if dp[i][j-m] > dp[i-1][m-1]:
        #                 l = m + 1
        #                 res = min(res, dp[i][j-m]) + 1
        #             elif dp[i][j-m] < dp[i-1][m-1]:
        #                 r = m - 1
        #                 res = min(res, dp[i-1][m-1]) + 1
        #             else:
        #                 res = dp[i-1][m-1] + 1
        #                 break
        #             # res = min(res, max(dp[i][j-m], dp[i-1][m-1])+1)
        #         dp[i][j] = res
        # return dp[k][n]

        """
        
        """
        # dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
        # f = 0
        # while dp[k][f] < n:
            # f += 1
            # for i in range(1, k+1):
                # dp[i][f] = dp[i][f-1] + dp[i-1][f-1] + 1
        # return f

        dp = [0 for i in range(k+1)]
        f = 0
        while dp[k] < n:
            for i in range(k, 0, -1):
                dp[i] = dp[i] + dp[i-1] + 1
            f += 1
        return f

# @lc code=end

